package com.sheng.leetcode.year2023.month06.day09;

import lombok.var;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/06/09
 * <p>
 * 2699. 修改图中的边权<p>
 * <p>
 * 给你一个 n 个节点的 无向带权连通 图，节点编号为 0 到 n - 1 ，再给你一个整数数组 edges ，<p>
 * 其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。<p>
 * 部分边的边权为 -1（wi = -1），其他边的边权都为 正 数（wi > 0）。<p>
 * 你需要将所有边权为 -1 的边都修改为范围 [1, 2 * 10^9] 中的 正整数 ，<p>
 * 使得从节点 source 到节点 destination 的 最短距离 为整数 target 。<p>
 * 如果有 多种 修改方案可以使 source 和 destination 之间的最短距离等于 target ，你可以返回任意一种方案。<p>
 * 如果存在使 source 到 destination 最短距离为 target 的方案，<p>
 * 请你按任意顺序返回包含所有边的数组（包括未修改边权的边）。如果不存在这样的方案，请你返回一个 空数组 。<p>
 * 注意：你不能修改一开始边权为正数的边。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5<p>
 * 输出：[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]<p>
 * 解释：上图展示了一个满足题意的修改方案，从 0 到 1 的最短距离为 5 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6<p>
 * 输出：[]<p>
 * 解释：上图是一开始的图。没有办法通过修改边权为 -1 的边，使得 0 到 2 的最短距离等于 6 ，所以返回一个空数组。<p>
 * <p>
 * 示例 3：<p>
 * 输入：n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6<p>
 * 输出：[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]<p>
 * 解释：上图展示了一个满足题意的修改方案，从 0 到 2 的最短距离为 6 。<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 100<p>
 * 1 <= edges.length <= n * (n - 1) / 2<p>
 * edges[i].length == 3<p>
 * 0 <= ai, bi < n<p>
 * wi = -1 或者 1 <= wi <= 10^7<p>
 * ai != bi<p>
 * 0 <= source, destination < n<p>
 * source != destination<p>
 * 1 <= target <= 10^9<p>
 * 输入的图是连通图，且没有自环和重边。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/modify-graph-edge-weights">2699. 修改图中的边权</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode2699 {

    @Test
    public void test01() {
//        int n = 5, source = 0, destination = 1, target = 5;
//        int[][] edges = {{4, 1, -1}, {2, 0, -1}, {0, 3, -1}, {4, 3, -1}};
//        int n = 3, source = 0, destination = 2, target = 6;
//        int[][] edges = {{0, 1, -1}, {0, 2, 5}};
        int n = 4, source = 0, destination = 2, target = 6;
        int[][] edges = {{1, 0, 4}, {1, 2, 3}, {2, 3, 5}, {0, 3, -1}};
        System.out.println(Arrays.deepToString(new Solution().modifiedGraphEdges(n, edges, source, destination, target)));
    }
}

class Solution {
    private final int inf = 2000000000;

    public int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        // edges[i] = {ai, bi, wi} 代表节点 ai 和 bi 之间存在一条边权为 wi 的边
        long d = dijkstra(edges, n, source, destination);
        if (d < target) {
            return new int[0][];
        }
        boolean ok = d == target;
        for (var e : edges) {
            if (e[2] > 0) {
                continue;
            }
            if (ok) {
                e[2] = inf;
                continue;
            }
            e[2] = 1;
            d = dijkstra(edges, n, source, destination);
            if (d <= target) {
                ok = true;
                e[2] += target - d;
            }
        }
        return ok ? edges : new int[0][];
    }

    private long dijkstra(int[][] edges, int n, int src, int dest) {
        int[][] g = new int[n][n];
        long[] dist = new long[n];
        Arrays.fill(dist, inf);
        dist[src] = 0;
        for (var f : g) {
            Arrays.fill(f, inf);
        }
        for (var e : edges) {
            int a = e[0], b = e[1], w = e[2];
            if (w == -1) {
                continue;
            }
            g[a][b] = w;
            g[b][a] = w;
        }
        boolean[] vis = new boolean[n];
        for (int i = 0; i < n; ++i) {
            int k = -1;
            for (int j = 0; j < n; ++j) {
                if (!vis[j] && (k == -1 || dist[k] > dist[j])) {
                    k = j;
                }
            }
            vis[k] = true;
            for (int j = 0; j < n; ++j) {
                dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
            }
        }
        return dist[dest];
    }
}
